2.5 Linked List

先前提到的的作法，都是預先配置記憶體空間後，才開始將資源放入。雖然簡單快速，但在決定預先配置空間尺寸，就變成一個需要進行評估的點。

• 預配空間過大，無法有效利用空間，造成多餘的浪費與成本耗損。
• 預配空間不足，置出來的記憶體空閒不足實際使用，導致重覆配置空間與搬移資料。

那是不是有方法可以動態的生成空間，而非仰賴事先配置的記憶體空間？

有的。那就是資料結構中所提到的鍵結串列(Linked List)。鍵結串列又分單向與雙向兩種，而這兩種都可以被運用在 Queue 的概念之中。

• 只有單純 FIFO 的 Queue，就適合使用單向的鍵結串列。
• 像是 Priority Queue，因為內部資源需要進行排序，雙向的鍵結串列就較為合適。

我們將每一個資源，視為一個節點。

當放入新的資源時，會將該資源放入節點中，同時將原本 Rear 的節點與新節點鍵結，並移到 Rear 到最後的節點。

反之，當資源離開時，Front 會向後移動一個節點，其他節點與 Rear 維持不動。

不管是單向鍵結或雙向鍵結，概念都是相同的。

下面的實作，採用單向鍵結的方式，來實作 Queue。
因為 .net core 之中，己經存有 LinkedList<T> ，所以取名為 LinkedListQueue<T>

 public class LinkedListQueue<T>
 {
     private class LinkedNode<T>
     {
         public T Data { set; get; }
         public LinkedNode<T> Next { set; get; }
     }

     private int _count = 0;
     private LinkedNode<T> _node = null;

     public void Enqueue(T data)
     {
         var node = new LinkedNode<T> {Data = data, Next = null};

         if (_node == null)
         {
             _node = node;
         }
         else
         {
             var ptr = _node;
             while (ptr.Next != null)
             {
                 ptr = ptr.Next;
             }

             ptr.Next = node;
         }

         _count++;
     }

     public bool IsEmpty => _count == 0;

     public T Dequeue()
     {
         if (_node == null)
             return default(T);

         var ptr = _node;

         _node = _node.Next;
         _count--;

         return ptr.Data;
     }
 }

2.6 延伸閱讀

1. Queue 相关数据结构的原理与实现 (LinkedList, ArrayDeque, PriorityQueue)
2. Queue: 以Array實作Queue
3. Linked List: 新增資料、刪除資料、反轉